package 中等.图.floyd;

import java.util.Arrays;

/**
 * 给你两个下标从 0 开始的字符串 source 和 target ，它们的长度均为 n 并且由 小写 英文字母组成。
 * 另给你两个下标从 0 开始的字符数组 original 和 changed ，以及一个整数数组 cost ，其中 cost[i]
 * 代表将字符 original[i] 更改为字符 changed[i] 的成本。
 * 你从字符串 source 开始。在一次操作中，如果 存在 任意 下标 j 满足 cost[j] == z  、original[j] == x
 * 以及 changed[j] == y 。你就可以选择字符串中的一个字符 x 并以 z 的成本将其更改为字符 y 。
 * 返回将字符串 source 转换为字符串 target 所需的 最小 成本。如果不可能完成转换，则返回 -1 。
 * 注意，可能存在下标 i 、j 使得 original[j] == original[i] 且 changed[j] == changed[i] 。
 *
 * @ https://leetcode.cn/problems/minimum-cost-to-convert-string-i/description/
 * @date 2024/07/01
 */
public class 转换字符串的最小成本I_2976 {

    public static void main(String[] args) {

        转换字符串的最小成本I_2976 impl = new 转换字符串的最小成本I_2976();

        System.out.println(impl.minimumCost("abcd", "acbe",
                new char[]{'a', 'b', 'c', 'c', 'e', 'd'},
                new char[]{'b', 'c', 'b', 'e', 'b', 'e'},
                new int[]{2, 5, 5, 1, 2, 20}));

    }

    /**
     * Floyd
     * 先求出每个字符 x 转换成 y 的最小成本，如果对应位置的字符不一致，则累计需要花费的成本
     */
    public long minimumCost(String source, String target, char[] original, char[] changed, int[] cost) {

        int[][] edges = new int[cost.length][3];

        for (int i = 0; i < cost.length; i++) {
            edges[i] = new int[]{original[i] - 'a', changed[i] - 'a', cost[i]};
        }

        int[][] minCost = findTheCity(27, edges);

        long ans = 0;

        for (int i = 0; i < target.length(); i++) {
            if (source.charAt(i) == target.charAt(i)) {
                continue;
            }
            int c = minCost[source.charAt(i) - 'a'][target.charAt(i) - 'a'];
            if (c >= Integer.MAX_VALUE / 2) {
                return -1;
            }
            ans += minCost[source.charAt(i) - 'a'][target.charAt(i) - 'a'];
        }

        return ans;
    }

    public int[][] findTheCity(int n, int[][] edges) {
        int[][] w = new int[n][n];
        for (int[] row : w) {
            Arrays.fill(row, Integer.MAX_VALUE / 2);
        }
        for (int[] edge : edges) {
            int x = edge[0], y = edge[1], cost = edge[2];
            w[x][y] = Math.min(w[x][y], cost);
        }
        int[][] dp = w;

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {

                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);

                }
            }
        }
        return dp;
    }

}
